package com.example.backtrack;

import java.util.*;

/**
 * 40. 组合总和 II
 * 给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
 * <p>
 * candidates 中的每个数字在每个组合中只能使用一次。
 * <p>
 * 注意：解集不能包含重复的组合。
 * <p>
 * 示例 1:
 * <p>
 * 输入: candidates = [10,1,2,7,6,1,5], target = 8,
 * 输出:
 * [
 * [1,1,6],
 * [1,2,5],
 * [1,7],
 * [2,6]
 * ]
 * <p>
 * 思路：这个题和数组组合I的区别是 每个元素只能用一次，所以遍历时用start+1，其它都一样
 * 注意点2：不能包含重复数组，这就
 */
public class CombinationSum2 {
    List<List<Integer>> res = new ArrayList<>();
    Deque<Integer> path;
    int[] candidates;
    boolean[] used;

    public static void main(String[] args) {
        int[] candidates = new int[]{10, 1, 2, 7, 6, 1, 5, 6, 6, 1, 1, 6};
        int target = 8;
        CombinationSum2 solution = new CombinationSum2();
        List<List<Integer>> res = solution.combinationSum2(candidates, target);
        System.out.println("输出 => " + res);
    }

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        this.candidates = candidates;
        used = new boolean[candidates.length];
        path = new LinkedList<>();
        Arrays.sort(candidates);//排序是为了剪枝
        back(0, target);
        return res;
    }

    public void back(int start, int target) {
        //在这控制target<=0return 也可以，就是会多走很多流程，如多余的在path中添加删除元素
        if (target == 0) {
            res.add(new ArrayList<>(path));
            return;
        }
        for (int i = start; i < candidates.length; i++) {
            if (!used[i]) {
                int candidate = candidates[i];
                if (target - candidate < 0) break;//在这里剪枝防止把多余元素加入path
                /**这里是主要的去重逻辑，因为题目要求不要有重复的组合，所以也就是在一个树枝上，也即会放入同一个结果数组的相同元素不用去重
                 * 但同一树层，也即不同数组的开头元素不可以相同，不然会出现重复的集合
                 * 所以判定时 i>start是为了比较时一定是有前面的元素的，也即i-1的元素也在当前结果集中
                 * candidates[i - 1] == candidates[i]是判定元素相同一般结合&&used[i-1]=false使用
                 * 也就是如果上一个重复元素没用过，那么当前元素肯定是开的新的结果数组，一定会出现重复集合
                 * 此处可以不用used暂时还没搞清楚,暂时只有这一个不需要，保险起见还是加上稳妥*/
                if (i > start && candidates[i - 1] == candidates[i] && !used[i - 1]) continue;//注意这里是i>start
                target -= candidate;
                used[i] = true;
                path.add(candidate);
                back(i + 1, target);
                used[i] = false;
                target += path.removeLast();
            }
        }
    }
}
